package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 11:18 2020/4/1
 * @Description BST第K大节点
 */

public class FaceTest_54 {

    /**
     * 思路：因为是求的是第K大的元素，因此不能使用中序遍历，需要使用中序遍历的逆序
     * 也就是右中左这样的顺序
     */
    int cutCout = 0;
    int ans = 0;

    public int kthLargest(TreeNode root, int k) {

        helper(root, k);
        return ans;

    }

    private void helper(TreeNode root, int k) {
        if (root == null) return;
        if (root.right != null) helper(root.right, k);
        if (++cutCout == k) {
            ans = root.val;
            return;
        }
        if (root.left != null) helper(root.left, k);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
